package com.cskaoyan.javase.recursion._3hanoi;

/**
 * 汉诺塔（Hanoi）问题，是经典的递归问题，学习递归一般都绕不开它，这里我们就学习一下如何使用递归求解汉诺塔问题。
 *
 * 首先看一下汉诺塔问题的描述：
 * 相传在古印度的圣庙中，有一种被称之为汉诺塔（也叫河内塔，Hanoi）的游戏
 * 简单来说：有三个塔1，2，3，塔1上有 N 个（N>1）穿孔圆盘，大盘在下，小盘在上
 * 要求按下列规则将所有圆盘移至塔3：
 * 	1，每次只能移动一个圆盘
 * 	2，大盘一定在小盘之下
 * 提示：可将圆盘临时置于塔2，也可以将塔1的圆盘重新移回塔1，但都必须遵循上述两条规则
 * 问：当塔1上有N（N>=1）个圆盘时，最少要移动多少次？（注意是最少）
 *
 * 通过玩N=2,和N=3的汉诺塔游戏,我们总结规律,并且我们是要用递归的思想求解问题的,所以我们就要往递归的思想上去靠,需要分解求解汉诺塔问题这个大规模的问题.
 *
 * 求解汉诺塔问题,必不可少的一步是,把塔1上最大的盘子,移到塔3上,这时塔3必须是空的
 *      所有的(除开最大的)盘子都要在塔2上
 * 于是求解汉诺塔问题就被分解成了三步:
 *      1.把最大盘子外的所有盘子,全部从塔1移到塔2
 *      2.把最大的盘子从塔1移到塔3
 *      3.把最大盘子外的所有盘子,全部从塔2移到塔3
 *
 * 现在设至少需要f(N)步,来完成N个盘子的汉诺塔问题,这时f(N)可以分解为:
 *      1.f(N-1)步
 *      2.1步
 *      3.f(N-1)步
 * 所以: f(N) = f(N-1) + 1 + f(N-1) 这就分解了汉诺塔问题,这就是递归的递归体
 * 接下来找递归的出口
 *      很明显上述分解不可能无休止的分解下去,因为N=1时,f(N) = 1 这就是递归的出口
 *
 * 递归的两要素都有了,可以开始写递归方法了.
 *
 * 通过等比数列的通项公式,求解汉诺塔问题的通项公式:
 * f(N) = f(N-1) + 1 + f(N-1)
 * f(N) + 1 = 2(f(N-1) + 1)
 * --->
 * f(N) = 2^n - 1
 *
 *
 * @since 10:43
 * @author wuguidong@cskaoyan.onaliyun.com
 */
public class Demo {
    public static void main(String[] args) {
        System.out.println(hanoi(100));
    }

    public static long hanoi(int n) {
        // 递归的出口
        if (n == 1) {
            return 1;
        }
        // 递归体
        return hanoi(n - 1) + 1 + hanoi(n - 1);
    }
}
